﻿class Solution {
    public int minDistance(String word1, String word2) {
if(word1.length()==0||word2.length()==0){
    return word1.length()+word2.length();
}
int m=word1.length();
int n=word2.length();
int[][]dp=new int[m+1][n+1];
//初始化边界值
for(int i=0;i<m+1;i++){
    dp[i][0]=i;
}
for(int i=0;i<n+1;i++){
    dp[0][i]=i;
}
for(int i=1;i<m+1;i++){
    for(int j=1;j<n+1;j++){
        int insert=dp[i][j-1]+1;
        int delete=dp[i-1][j]+1;
        int change=dp[i-1][j-1];
        if(word1.charAt(i-1)!=word2.charAt(j-1)){
            change+=1;
        }
    
    dp[i][j]=Math.min(insert,Math.min(delete,change));
    }
}
return dp[m][n];
    }
}